package com.hy.study.huffmantree;

import java.util.ArrayList;
import java.util.Collections;

public class HuffmanTree {
    public static void main(String[] args) {
        int arr[] = {13, 7, 8, 3, 29, 6, 1};
        //返回创建之后的huffman 树的root 节点
        Node root = createHuffmanTree(arr);
        //使用前序遍历
        preOrder(root);

    }


    public static void preOrder(Node root) {
        if (root == null) {
            System.out.println("该树是一个空树，无法遍历");
            return;
        } else {
            root.preOrder();
        }
    }

    /**
     * 构建haffman 树
     *
     * @param arr
     */
    public static Node createHuffmanTree(int[] arr) {
        ArrayList<Node> nodes = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            Node node = new Node(arr[i]);
            nodes.add(node);
        }
        //最后ArrayList 中只有一个节点
        while (nodes.size() > 1) {
            //从小到大排序
            Collections.sort(nodes);
            //(1) 取出权值最小的两个节点
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            //构建一颗新的二叉树
            Node parent = new Node(leftNode.getValue() + rightNode.getValue());
            parent.setLeft(leftNode);
            parent.setRight(rightNode);
            //从ArrayList中删除掉处理过的二叉树
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            //将parent节点加入到Node中
            nodes.add(parent);
        }
        //返回huffManTree root
        return nodes.get(0);
    }


}

/**
 * 创建节点类
 * 为了让Node 对象 支持排序 这里需要实现comparent接口
 */
class Node implements Comparable<Node> {
    private int value;//节点权值
    private Node left;//指向左子节点的
    private Node right;//指向右子节点

    public Node(int value) {
        this.value = value;
    }

    public Node(Node right) {
        this.right = right;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    @Override
    public int compareTo(Node o) {
        // 表示从小到大排序
        return this.value - o.value;
    }


    public void preOrder() {
        System.out.println(this);
        if (this.getLeft() != null) {
            this.getLeft().preOrder();
        }
        if (this.getRight() != null) {
            this.getRight().preOrder();
        }
    }
}